COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14 pt

\leftline{\sevenrm puzzle.tex[pap,mps] \today}
\leftline{\copyright \sevenrm Robert W. Floyd, May 1988}
\bigskip

\noindent{\bf Problem (Advanced)}

On a certain island, the hunters are the married men; the gatherers of food
plants are the married women.  The Ministry of Hunting divided the island into
as many hunting ranges of equal size as there were married couples.  Working
independently, the Ministry of Seeds and Fruit divided the island into the same
number of gathering ranges, also of equal size.  When it was time for the ranges
to be assigned to couples, the Ministry of Marriage insisted that the hunting
range and the gathering range assigned to each couple should be close together.
It turned out, to everyone's surprise, that it was possible to assign them so
that each couple's two ranges overlapped; in fact, it became the national custom
to build conjugal huts on the ground common to both ranges.  The Ministry of
Religion declared that the possibility of doing this was a miracle.  Show them
wrong by exhibiting a positive lower bound on the area available for the huts.

\smallskip
\noindent{\bf Solution by the Proposer:}

Let $n$ be the number of couples.  Let the unit of area be the size of one
range.

Let $H$ be any set of $k$ hunting ranges.  Rank the
gathering ranges as $g↓1$ to $g↓n$ in order of decreasing area of $H∩g↓i$.
If the area of $H∩g↓k$ is $\alpha$, then 
$$\displaylines {k = \hbox{ area }\, H = \sum ↓{1 \le i \le k-1} \hbox { area }\,
(H∩g↓i) + \sum ↓{k \le i \le n} \hbox { area }\, (H∩g↓i) \cr
\quad \le \sum ↓{1 \le i \le k-1}
\hbox { area }\, g↓i + (n+1-k) \alpha = k-1 + (n+1-k) \alpha\,\cr}$$ so
$\alpha \ge \displaystyle{1 \over n+1-k}$.
For each $1 \le i \le k$, area $(H∩g↓i) \ge \displaystyle {1 \over n+1-k}$, so
for some $h \in H$, area $(h∩g↓i) \ge \displaystyle {1 \over k(n+1-k)} \ge
\displaystyle {4 \over (n+1)↑2}$.  Let $\mu$ be the relation between hunting
range $h$ and gathering range $g$ such that $h \mu g$ iff
area $(h∩g) \ge \displaystyle {4 \over (n+1)↑2}$.
We have shown that for any set $H$ of $k$ hunting ranges, the image of $H$
under $\mu$ has cardinality at least $k$.  This satisfies the condition of
Philip Hall's theorem on 
bipartite matchings[2,~1]; therefore, the relation $\mu$ contains
a one-to-one matching of hunting ranges with gathering ranges, where 
matched ranges overlap by at least $\displaystyle {4 \over (n+1)↑2}$.

To show that this is the best possible result, let $n=2k-1$.  Let $H$ 
be a union of $k$ hunting ranges and $G$ be a 
union of $k-1$ gathering ranges.  Let the area of $g∩h$ be 
$ 1 \over k$ if $(g \in G) ≡ (h \in H)$ and $\displaystyle{1 \over k↑2} = 
\displaystyle {4\over (n+1)↑2}$ otherwise.
Some range in $H$ must be matched with a range not in $G$, with overlapping area
$\displaystyle{4 \over (n+1)↑2}$.

\noindent{\bf References}

\noindent1  Marshall Hall, {\it Combinatorial Theory}, Blaisdell, 1967, Ch. 5.

\noindent2  Paul R. Halmos and Herbert E. Vaughan, The Marriage Problem, Amer. 
Jnl. of Math. 72, 1950, pp 214-215.

\bye